#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;
// 560.和为k的子数组
//给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数。
//子数组是数组中元素的连续非空序列。
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int count = 0;
        int n = nums.size();
        // 计算前缀和
        vector<int> pre(n,0);
        pre[0] = nums[0];
        for(int i = 1; i < n; i++) {
            pre[i] = pre[i-1] + nums[i];
        }

        unordered_map<int, int> map;    // <前缀和：出现次数>
        map[0] = 1; // 和为0的次数为1
        for(int i = 0; i < n; i++) {
            count += map[pre[i] - k];
            map[pre[i]]++;
        }
        return count;
    }
};
int main() {
    vector<int> nums = {1,1,1};
    std::cout << Solution().subarraySum(nums,2) << std::endl;   // 2
    nums = {1,2,3};
    std::cout << Solution().subarraySum(nums,3) << std::endl;   // 2
    nums = {3,4,7,2,-3,1,4,2};
    std::cout << Solution().subarraySum(nums,7) << std::endl;   // 4
    return 0;
}
